package com.alibaba.interview;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author ZhangyiA
 * @describe: 过河时间最短问题
 * 题目分析： 记人数为 n
 * if n > 4 时 , 过河时先将最重的两个人渡过去 , 此时有两种方案 , ( 最终方案是船回到起始位置 此时河边仍然有两个人 . )
 * 1. 最轻的人走两次 , 每次带一个最重的人过去 ;
 *    时间 time = 2 * t[1] + t[n] + t[n - 1]
 * 2. 先最轻的两个人一起过去 , 最轻的回来 , 最重的两个一起过去 , 次轻回来 ;
 *    时间 time = t[2] + t[n] + t[1] + t[2] = t[1] + 2 * t[2] + t[n]
 * @date 2021/07/03
 */

public class Three_GoesToSpringOuting {

    public long getMinCostTime(int[] t){
        int n = t.length - 1;
        Arrays.sort(t);
        long time = 0;
        while(n >= 4){
            time += Math.min(2 * t[1] + t[n] + t[n - 1] , t[1] + 2 * t[2] + t[n]);
            n -= 2;
        }
        if(n == 3){
            time += t[1] + t[2] + t[3];
        } else if(n == 2) {
            time += t[2];
        } else if(n == 1) {
            time += t[1];
        }
        return time;
    }


    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        Three_GoesToSpringOuting springOuting = new Three_GoesToSpringOuting();
        int T = input.nextInt();
        while(T -- > 0){
            int n = input.nextInt();
            int[] time = new int[n + 1];
            for(int i = 1 ; i <= n ; i ++){
                time[i] = input.nextInt();
            }
            System.out.println(springOuting.getMinCostTime(time));
        }
    }

}
